{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 其他数据结构[可选]\n",
    "\n",
    "该 notebook 的目的是展示一些你可以使用的其他数据结构，但不会涉及太多细节。你可以通过阅读[Python 收藏库中的文档](https://docs.python.org/3.3/library/collections.html)了解更多信息。\n",
    "\n",
    "## 1. 元组\n",
    "\n",
    "这是我们尚未讨论的唯一标准库数据结构。 元组是Python对象的非可变（不可更改）序列。\n",
    "\n",
    "该元组与列表非常相似。你可以通过阅读[Python 元组文档](https://docs.python.org/3/tutorial/datastructures.html#tuples-and-sequences)了解更多相关信息。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(1, 2, 3)\n",
      "<class 'tuple'>\n"
     ]
    }
   ],
   "source": [
    "# tuples are created with (parentheses)\n",
    "\n",
    "my_tuple = (1,2,3)\n",
    "print(my_tuple)\n",
    "print(type(my_tuple))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "2\n",
      "3\n"
     ]
    }
   ],
   "source": [
    "# elements can be accessed just like they are with lists.\n",
    "\n",
    "print( my_tuple[0] )\n",
    "print( my_tuple[1] )\n",
    "print( my_tuple[2] )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "ename": "TypeError",
     "evalue": "'tuple' object does not support item assignment",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mTypeError\u001b[0m                                 Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-3-c5caf46120c9>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[1;32m      2\u001b[0m \u001b[0;31m# due to them being immutable.\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      3\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 4\u001b[0;31m \u001b[0mmy_tuple\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;36m4\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;31mTypeError\u001b[0m: 'tuple' object does not support item assignment"
     ]
    }
   ],
   "source": [
    "# there are some things you can't do with tuples \n",
    "# due to them being immutable.\n",
    "\n",
    "my_tuple[1] = 4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{('a', 'b', 'c'), (1, 2, 3)}\n"
     ]
    }
   ],
   "source": [
    "# but there are also some things you CAN do with tuples\n",
    "# that you can't do with lists...\n",
    "\n",
    "t1 = ('a','b','c')\n",
    "t2 = (1, 2, 3)\n",
    "\n",
    "set_of_tuples = set()\n",
    "\n",
    "set_of_tuples.add(t1)\n",
    "set_of_tuples.add(t2)\n",
    "\n",
    "print(set_of_tuples)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "ename": "TypeError",
     "evalue": "unhashable type: 'list'",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mTypeError\u001b[0m                                 Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-5-4b4d5a49a68e>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[1;32m      4\u001b[0m \u001b[0mset_of_lists\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mset\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      5\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 6\u001b[0;31m \u001b[0mset_of_lists\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0madd\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mL1\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m      7\u001b[0m \u001b[0mset_of_lists\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0madd\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mL2\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      8\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;31mTypeError\u001b[0m: unhashable type: 'list'"
     ]
    }
   ],
   "source": [
    "L1 = ['a','b','c']\n",
    "L2 = [1, 2, 3]\n",
    "\n",
    "set_of_lists = set()\n",
    "\n",
    "set_of_lists.add(L1)\n",
    "set_of_lists.add(L2)\n",
    "\n",
    "print(set_of_lists)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2. 可命名元组\n",
    "\n",
    "可命名元组非常类似于元组，除了字段也可以被命名！ 当我想用`object.property`表示法但不想定义完整的类时，就可以使用可命名元组。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Point(x=5, y=-3)\n"
     ]
    }
   ],
   "source": [
    "# named tuple's need to be imported from the collections library\n",
    "from collections import namedtuple\n",
    "\n",
    "# here we define Point as a new type of thing. \n",
    "# It has properties x and y.\n",
    "Point = namedtuple(\"Point\", [\"x\", \"y\"])\n",
    "\n",
    "# here we actually instantiate a point\n",
    "p1 = Point(5, -3)\n",
    "\n",
    "print(p1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5\n",
      "-3\n"
     ]
    }
   ],
   "source": [
    "# there are two ways to access the fields in a point...\n",
    "\n",
    "# ... by position\n",
    "print( p1[0] )\n",
    "print( p1[1] )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5\n",
      "-3\n"
     ]
    }
   ],
   "source": [
    "# ... or by name\n",
    "\n",
    "print( p1.x )\n",
    "print( p1.y )"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3. 计数器\n",
    "我们经常需要计算事情发生的次数。 下面的代码演示了如何使用`Counter`来计算字符串中各种字符的出现次数。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(' ', 8),\n",
       " ('e', 4),\n",
       " ('o', 4),\n",
       " ('t', 2),\n",
       " ('h', 2),\n",
       " ('u', 2),\n",
       " ('r', 2),\n",
       " ('d', 2),\n",
       " ('q', 1),\n",
       " ('i', 1),\n",
       " ('c', 1),\n",
       " ('k', 1),\n",
       " ('b', 1),\n",
       " ('w', 1),\n",
       " ('n', 1),\n",
       " ('f', 1),\n",
       " ('x', 1),\n",
       " ('j', 1),\n",
       " ('m', 1),\n",
       " ('p', 1),\n",
       " ('v', 1),\n",
       " ('l', 1),\n",
       " ('a', 1),\n",
       " ('z', 1),\n",
       " ('y', 1),\n",
       " ('g', 1)]"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from collections import Counter\n",
    "\n",
    "string = \"the quick brown fox jumped over the lazy dog\"\n",
    "\n",
    "character_counter = Counter()\n",
    "for character in string:\n",
    "    character_counter[character] += 1\n",
    "    \n",
    "character_counter.most_common()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "这个字符串看起来有8个空格，4个e's，4个o's 等......"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n"
     ]
    }
   ],
   "source": [
    "# something that's nice about counters is that they don't throw \n",
    "# an error if you try to access a key that isn't there. Instead\n",
    "# they return 0.\n",
    "\n",
    "# how many capital A's are in the string above?\n",
    "\n",
    "print(character_counter[\"A\"])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n"
     ]
    }
   ],
   "source": [
    "# but how many lowercase a's?\n",
    "\n",
    "print(character_counter[\"a\"])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4. 默认字典\n",
    "\n",
    "默认字典最好通过示例来解释。让我们回到之前的“三盒门票”例子。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'low': [{'priority': 'low', 'description': 'windshield chipped'}, {'priority': 'low', 'description': 'failed to use turn signal'}], 'medium': [{'priority': 'medium', 'description': 'did not come to complete stop at stop sign'}], 'high': [{'priority': 'high', 'description': 'slammed on brakes'}]}\n"
     ]
    }
   ],
   "source": [
    "TICKET_BOXES = {\n",
    "    \"low\"    : [],\n",
    "    \"medium\" : [],\n",
    "    \"high\"   : []\n",
    "}\n",
    "\n",
    "unfiled_tickets = [\n",
    "    {\n",
    "        \"priority\"    : \"high\",\n",
    "        \"description\" : \"slammed on brakes\"\n",
    "    },\n",
    "    {\n",
    "        \"priority\"    : \"low\",\n",
    "        \"description\" : \"windshield chipped\"\n",
    "    },\n",
    "    {\n",
    "        \"priority\"    : \"low\",\n",
    "        \"description\" : \"failed to use turn signal\"\n",
    "    }\n",
    "    ,\n",
    "    {\n",
    "        \"priority\"    : \"medium\",\n",
    "        \"description\" : \"did not come to complete stop at stop sign\"\n",
    "    }\n",
    "]\n",
    "\n",
    "def file_ticket(ticket):\n",
    "    priority = ticket['priority']\n",
    "    TICKET_BOXES[priority].append(ticket)\n",
    "    \n",
    "for ticket in unfiled_tickets:\n",
    "    file_ticket(ticket)\n",
    "    \n",
    "print(TICKET_BOXES)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "ename": "KeyError",
     "evalue": "'highest'",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mKeyError\u001b[0m                                  Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-20-0d6e7dcf92da>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[1;32m      7\u001b[0m }\n\u001b[1;32m      8\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 9\u001b[0;31m \u001b[0mfile_ticket\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mnew_ticket\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;32m<ipython-input-19-44880f72c04b>\u001b[0m in \u001b[0;36mfile_ticket\u001b[0;34m(ticket)\u001b[0m\n\u001b[1;32m     27\u001b[0m \u001b[0;32mdef\u001b[0m \u001b[0mfile_ticket\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mticket\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     28\u001b[0m     \u001b[0mpriority\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mticket\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;34m'priority'\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 29\u001b[0;31m     \u001b[0mTICKET_BOXES\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mpriority\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mappend\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mticket\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     30\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     31\u001b[0m \u001b[0;32mfor\u001b[0m \u001b[0mticket\u001b[0m \u001b[0;32min\u001b[0m \u001b[0munfiled_tickets\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;31mKeyError\u001b[0m: 'highest'"
     ]
    }
   ],
   "source": [
    "# so far so good! But what if we try to file a ticket\n",
    "# with a priority \"highest\" (as we saw in Jira)?\n",
    "\n",
    "new_ticket = {\n",
    "    \"priority\" : \"highest\",\n",
    "    \"description\": \"vehicle crashed!\"\n",
    "}\n",
    "\n",
    "file_ticket(new_ticket)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'low': [{'priority': 'low', 'description': 'windshield chipped'}, {'priority': 'low', 'description': 'failed to use turn signal'}], 'medium': [{'priority': 'medium', 'description': 'did not come to complete stop at stop sign'}], 'high': [{'priority': 'high', 'description': 'slammed on brakes'}], 'highest': [{'priority': 'highest', 'description': 'vehicle crashed!'}]}\n"
     ]
    }
   ],
   "source": [
    "# as expected, we get a key error... one way to fix this\n",
    "# is as follows\n",
    "\n",
    "def file_ticket_fixed(ticket):\n",
    "    priority = ticket['priority']\n",
    "    \n",
    "    # new code\n",
    "    if priority not in TICKET_BOXES:\n",
    "        TICKET_BOXES[priority] = []\n",
    "        \n",
    "    TICKET_BOXES[priority].append(ticket)\n",
    "\n",
    "file_ticket_fixed(new_ticket)\n",
    "print(TICKET_BOXES)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "defaultdict(<class 'list'>, {'high': [{'priority': 'high', 'description': 'slammed on brakes'}], 'low': [{'priority': 'low', 'description': 'windshield chipped'}, {'priority': 'low', 'description': 'failed to use turn signal'}], 'medium': [{'priority': 'medium', 'description': 'did not come to complete stop at stop sign'}], 'highest': [{'priority': 'highest', 'description': 'vehicle crashed!'}]})\n"
     ]
    }
   ],
   "source": [
    "# OR we can use a \"defaultdict\" \n",
    "from collections import defaultdict\n",
    "\n",
    "TICKET_BOXES = defaultdict(list) # notice the argument of list...\n",
    "\n",
    "def file_ticket(ticket):\n",
    "    priority = ticket['priority']\n",
    "    TICKET_BOXES[priority].append(ticket)\n",
    "\n",
    "for ticket in unfiled_tickets:\n",
    "    file_ticket(ticket)\n",
    "    \n",
    "file_ticket(new_ticket)\n",
    "\n",
    "print(TICKET_BOXES)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "当你尝试访问不存在的密钥时，默认字典会将该密钥添加到字典中，并将**默认**值与其关联（在本例中为列表）。\n",
    "\n",
    "如果你想了解更多信息，可以阅读 [关于默认字典的文档](https://docs.python.org/3.3/library/collections.html#collections.defaultdict) 。\n",
    "\n",
    "## 5. 来自`collections`的其他数据结构"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import deque, OrderedDict"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "deque([4, 5, 6])\n"
     ]
    }
   ],
   "source": [
    "d = deque([4,5,6])\n",
    "print(d)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "deque([4, 5, 6, 7])\n"
     ]
    }
   ],
   "source": [
    "d.append(7)\n",
    "print(d)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "deque([3, 4, 5, 6, 7])\n"
     ]
    }
   ],
   "source": [
    "d.appendleft(3)\n",
    "print(d)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "last element was 7\n",
      "now d is deque([3, 4, 5, 6])\n"
     ]
    }
   ],
   "source": [
    "last = d.pop()\n",
    "print(\"last element was\", last)\n",
    "print(\"now d is\", d)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "first element was 3\n",
      "now d is deque([4, 5, 6])\n"
     ]
    }
   ],
   "source": [
    "first = d.popleft()\n",
    "print(\"first element was\", first)\n",
    "print(\"now d is\", d)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [],
   "source": [
    "# # # # #"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [],
   "source": [
    "od = OrderedDict()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [],
   "source": [
    "od['a'] = 1\n",
    "od['b'] = 2\n",
    "od['c'] = 3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "OrderedDict([('a', 1), ('b', 2), ('c', 3)])\n"
     ]
    }
   ],
   "source": [
    "# as the name implies, an OrderedDict is a dictionary that\n",
    "# keeps track of the order in which elements were added.\n",
    "\n",
    "print(od)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.5"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  },
  "varInspector": {
   "cols": {
    "lenName": 16,
    "lenType": 16,
    "lenVar": 40
   },
   "kernels_config": {
    "python": {
     "delete_cmd_postfix": "",
     "delete_cmd_prefix": "del ",
     "library": "var_list.py",
     "varRefreshCmd": "print(var_dic_list())"
    },
    "r": {
     "delete_cmd_postfix": ") ",
     "delete_cmd_prefix": "rm(",
     "library": "var_list.r",
     "varRefreshCmd": "cat(var_dic_list()) "
    }
   },
   "types_to_exclude": [
    "module",
    "function",
    "builtin_function_or_method",
    "instance",
    "_Feature"
   ],
   "window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
